139. 单词拆分

Similar Question

Solution Tips

方案一: 记忆化搜索 + 回溯法

var wordBreak = function(s, wordDict) {
    // 要往背包上靠, 也太反直觉了吧, 想想不用背包要怎么处理
    // 回溯法 + 记忆化搜索好像可以解决? 只要记住截断之后的字符串, 是否可以解决即可
    const memo = [];
    backtracking(s)
    return !!memo[s];

    function backtracking(rest) {
        if (rest.length === 0) return true;

        if (memo[rest] !== undefined) return memo[rest];

        // 二叉树思路
        for (let i = 0; i < wordDict.length; i++) {
            // 选择使用 w[i] 拼接
            let restPart = rest.replace(wordDict[i], ',');
            if (restPart !== rest) {
                let restArray = restPart.split(',');
                // 全部通过才可以 true
                memo[rest] = restArray.every((part) => {
                    return backtracking(part)
                })
                if (memo[rest]) {
                    break;
                }
            }
        }

        return memo[rest]
    }
};

// let s = "leetcode", wordDict = ["leet", "code"]
// let s = "applepenapple", wordDict = ["apple", "pen"]
let s = "dogs", wordDict = ['dog', 's','gs']
console.log(wordBreak(s, wordDict));

方案二: 记忆化搜索二

方案一的匹配方案, 需要替换 + 阶段 + 遍历阶段, 逻辑太复杂了

可以考虑遍历字符串, 只匹配字符串的 start

const wordBreak = (s, wordDict) => {
    const len = s.length;
    const wordSet = new Set(wordDict);
    const memo = new Array(len);

    // 递归的入口，从0到末尾的子串能否break
    return canBreak(0);

    // 判断从start到末尾的子串能否break
    function canBreak (start) {
        //指针越界，s一步步成功划分为单词，才走到越界这步，现在没有剩余子串
        if (start == len) {
            //返回真，结束递归
            return true;
        }
        // 判断 memo 是否有值, 只在此处进行即可
        // memo中有，就用memo中的
        if (memo[start] !== undefined) return memo[start];

        //指针i去划分两部分，for枚举出当前所有的选项i
        for (let i = start + 1; i <= len; i++) {
            // 切出的前缀部分
            const prefix = s.slice(start, i);
            // 前缀部分是单词，且剩余子串能break，返回真
            if (wordSet.has(prefix) && canBreak(i)) {
                // 当前递归的结果存一下
                memo[start] = true;
                return true;
            }
            // 如果前缀部分不是单词，就不会执行canBreak(i)。进入下一轮迭代，再切出一个前缀串，再试
        }
        // 指针i怎么划分，都没有返回true，则返回false
        // 当前递归的结果存一下
        memo[start] = false;
        return false;
    }
}

方案三: 动态规划

分割字符的思路是和方案二一致的, 怪不得我先入为主的使用方案一, 结果想不出动态规划的做法

const wordBreak = (s, wordDict) => {

    let dp = Array(s.length + 1).fill(false);
    dp[0] = true;

    for(let i = 0; i <= s.length; i++){
        for(let j = 0; j < wordDict.length; j++) {
            if(i >= wordDict[j].length) {
                if(s.slice(i - wordDict[j].length, i) === wordDict[j] && dp[i - wordDict[j].length]) {
                    dp[i] = true
                }
            }
        }
    }

    return dp[s.length];
}